In unstructured peer-to-peer (P2P) networks, the overlay topology (orconnectivity graph) among peers is a crucial component in addition to thepeer/data organization and search. Topological characteristics have profoundimpact on the efficiency of search on such unstructured P2P networks as well asother networks. It has been well-known that search on small-world topologies ofN nodes can be as efficient as O(ln N), while scale-free (power-law) topologiesoffer even better search efficiencies like as good as O(lnln N) for a range ofdegree distribution exponents. However, generation and maintenance of suchscale-free topologies are hard to realize in a distributed and potentiallyuncooperative environments as in the P2P networks. A key limitation ofscale-free topologies is the high load (i.e. high degree) on very few number ofhub nodes. In a typical unstructured P2P network, peers are not willing tomaintain high degrees/loads as they may not want to store large number ofentries for construction of the overlay topology. So, to achieve fairness andpracticality among all peers, hard cutoffs on the number of entries are imposedby the individual peers, which limits scale-freeness of the overall topology.Thus, efficiency of the flooding search reduces as the size of the hard cutoffdoes. We investigate construction of scale-free topologies with hard cutoffs(i.e. there are not any major hubs) and effect of these hard cutoffs on thesearch efficiency. Interestingly, we observe that the efficiency of normalizedflooding and random walk search algorithms increases as the hard cutoffdecreases.
展开▼
